

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Date;


import lpsolve.*;

public class Main {

	  public static void main(String[] args) {
		  	try {
		  		
		  		Date start = new Date();
		  		long startTime = start.getTime();
		  		
		  		String sudokuInput = null;
		 	  		
		        // number of the variables/columns 
		  		final int Ncol = 729;
		  		InputStreamReader converter = new InputStreamReader(System.in);
		  		BufferedReader in = new BufferedReader(converter);
		  		
		  		//get the sudoku from the user
		  		try {
		  			sudokuInput = in.readLine();
		  			//System.out.println(sudokuInput);
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}

		    	// Create a problem with 4 variables and 0 constraints
		      LpSolve solver = LpSolve.makeLp(0, Ncol);
		      
		      //update that the variables will be integer
		      for(int i=1; i<=729; i++){
		    	 solver.setInt(i, true);
		      }		      
		      
	          int[] colno = new int[Ncol];
	          double[] row = new double[Ncol];

		      
		      //-------insure that in every square will be just one of the values ----------
		      //go over the constrains
		      for(int j=1; j<=81; j++){
		    	  //create the colno and rows
		    	  for(int i=0; i<729; i++){
		    		  if(((9*(j-1))<(i+1))&&((i+1)<=(9*j))){
		    			  //solver.setMat(j, i, 1); 
		    	          colno[i] = i+1; 
		    	          row[i] = 1;
		    		  }
		    		  else{
		    	          colno[i] = i+1; 
		    	          row[i] = 0; 
		    		  }
		    	  }
		    	  
		    	  solver.addConstraintex(Ncol, row, colno, LpSolve.EQ, 1);
		      }
		      
		     
		    //-------insure that in every value appear just once in row----------
		      //the two first for will over the rows in the matrix
		      //for jumping in the values in the binary variables
		      for(int j=1; j<=9; j++){
		    	  //for jumping in the rows in the binary variables
		    	  for(int k=1; k<=9; k++){
		    		  
			    	  for(int i=1; i<=729; i++){
			    		  //i-j Divisor 9 and 81(k-1)<i<=81k 
			    		  if((((i-j)%9)==0)&&(((81*(k-1))<i)&&(i<=(81*k)))){
			    	          colno[i-1] = i; 
			    	          row[i-1] = 1;			    			  
			    			  //solver.setMat(9*(j-1)+k+81, i, 1); 
			    		  }
			    		  else{
			    	          colno[i-1] = i; 
			    	          row[i-1] = 0;	
			    			  //solver.setMat(9*(j-1)+k+81, i, 0); 
			    		  }
			    	  }
			    	  //create the constrain
			    	  solver.addConstraintex(Ncol, row, colno, LpSolve.EQ, 1);
		    	  } 
		      }
		    	
		      		        	
			    //-------insure that in every value appear just once in column----------
		      //the two first for will add the constrain
		      
		      //for jumping in the rows in the binary variables
		      for(int j=0; j<9; j++){
		    	  //for jumping in the values in the binary variables
		    	  for(int k=0; k<9; k++){
		    		  
			    	  for(int i=0; i<729; i++){
			    		  //(i-9j-k) Divisor  81
			    		  if(((i-(9*j)-k)%81)==0){
			    	          colno[i] = i+1; 
			    	          row[i] = 1;		 
			    		  }
			    		  else{
			    	          colno[i] = i+1; 
			    	          row[i] = 0;			    			  
			    		  }
			    	  }
			    	  //create the constrain
			    	  solver.addConstraintex(Ncol, row, colno, LpSolve.EQ, 1);
		    	  } 
		      }		      
		      
		     
			    //-------insure that in every value appear just once in every box(3X3)----------		      
		      
		      
		      //for progress in the values (j=0 its for value 1, j=1 for value 2 ...)
		      for(int j=0; j<9; j++){
		    	  //for jumping in the values in the binary variables
		    	  for(int k=0; k<3; k++){
		    		  for(int r=0; r<3; r++){
				    	  for(int i=0; i<729; i++){
				    		  //(i-j) Divisor  9 - that way every for every j will be checking different value
				    		  //the second condition will determine in which box(3X3 in sudoku) is the i
				    		  if(((i-j)%9==0)&&
				    				  (((((27*r)+(243*k))<=i)&&(i<((27*(r+1))+(243*(k)))))||((((27*r)+(243*k)+81)<=i)&&((i<((27*(r+1))+81+(243*(k))))))||((((27*r)+(243*k)+162)<=i)&&((i<((27*(r+1))+162+(243*(k)))))))){
				    	          colno[i] = i+1; 
				    	          row[i] = 1;		 
				    		  }
				    		  else{
				    	          colno[i] = i+1; 
				    	          row[i] = 0;			    			  
				    		  }
				    	  }
				    	  //create the constrain
				    	  solver.addConstraintex(Ncol, row, colno, LpSolve.EQ, 1);
		    		  }
		    		  
		    	  } 
		      }	
		      
		      
		      //The starting numbers are entered as constraints
		      for(int j=0; j<81; j++){
	    		  //in case that the number is not zero(zero mean empty place)
	    		  if(sudokuInput.charAt(j) != '0'){
	    			  // prepare for create the constrain
			    	  for(int i=0; i<729; i++){
		    	          colno[i] = i+1; 
		    	          row[i] = 0;
			    	  }
			    	  //get the digit in rhe sudoku
			    	  String strNum = sudokuInput.substring(j, j+1);
			    	  //System.out.println("strNum = " + strNum);
			    	  int num = Integer.parseInt(strNum);
			    	  //System.out.println("num = " + num);
			    	  //update the row
			    	  row[9*j + num -1] = 1;
			    	  
			    	  //create the constrain
			    	  solver.addConstraintex(Ncol, row, colno, LpSolve.EQ, 1);
	    		  }

		      }
		      
		      
		      /*
		      // add constraints
		      solver.strAddConstraint("3 2 2 1", LpSolve.LE, 4);
		      solver.strAddConstraint("0 4 3 1", LpSolve.GE, 3);

		      // set objective function
		      solver.strSetObjFn("2 3 -2 3");
				*/
		      
		      
		      // solve the problem
		      solver.solve();
		      
		      //get the values of the variables
		      double[] var = solver.getPtrVariables();
		     /*
		      // print solution
		      System.out.println("Value of objective function: " + solver.getObjective());
		      
		      for (int i = 0; i < var.length; i++) {
		        System.out.println("Value of var[" + i + "] = " + var[i]);
		      }
				*/
		      
		      System.out.println("---------------------------------------------------------------------------------------------------------------");		      System.out.println("The sudoku solution is:");
		      // print solution
		      for (int i = 0; i < var.length; i++) {
		        //System.out.println("Value of var[" + i + "] = " + var[i]);
		    	  //if the binary variable is true
		    	  if(var[i] == 1){
		    		  int digit = (i)%9;
		    		  //switch case for clarification of the value
		    		  switch(digit){
		    		  		case 0:	System.out.print("1");
		    		  			break;
		    		  		case 1:	System.out.print("2");
	    		  				break;	
		    		  		case 2:	System.out.print("3");
	    		  				break;
		    		  		case 3:	System.out.print("4");
		    		  			break;
		    		  		case 4:	System.out.print("5");
	    		  				break;
		    		  		case 5:	System.out.print("6");
	    		  				break;	
		    		  		case 6:	System.out.print("7");
	    		  				break;
		    		  		case 7:	System.out.print("8");
		    		  			break;		    		  		
		    		  		case 8:	System.out.print("9");
		    		  			break;			    		  		
		    		  }//end of the switch
		    	  }//end of the if
		      }		
		      
		      System.out.println("");
		      System.out.println("---------------------------------------------------------------------------------------------------------------");
		      System.out.println("");
		      
		      
		      
		  		Date end = new Date();
		  		long endTime = end.getTime();
		  		System.out.println("The run time in miliseconds: " + (endTime - startTime));
			    System.out.println("---------------------------------------------------------------------------------------------------------------");
			    System.out.println("");
		  	//delete the problem and free memory
		      solver.deleteLp();
		      
		    }
		    catch (LpSolveException e) {
		       e.printStackTrace();
		    }
		  }

}
